---
title: "货仓选址"
created: 2025-11-28
tags:
  - 算法
---

# 货仓选址

## 题目 [货仓选址](https://www.acwing.com/problem/content/106/)

![[image-c0e8cc14.png]]

## 思路分析

一个常识性的问题 若要选两个点的最近位置 肯定是在中间吧

![[image-6ce0f7b6.png]]

那拓展成多个点 如果是三角形的话可能就得取垂直平分线了 可是这里还是一维的

那其实到各点距离最短的地方仍是中间位置

分情况讨论了 如果是奇数个时 中位数只有一个 取它即可 若为偶数个时 中位数有两个 任取一个都行

统一一下 成n/2向下取整

**证明：**

把A[0]~A[N-1]排序，设货仓在X坐标处，X左侧的商店有P家，右侧的商店有Q家。若P < Q，则每把仓库的选址向右移动1单位距离，距离之和就会变少Q
- P.同理，若P > Q，则仓库的选址向左移动会使距离之和变小。当P==Q时为最优解。

因此仓库应该建在中位数处，把A进行排序，

当N为奇数时，货仓建在A[(N - 1)/2]处，

当N为偶数时，仓库建在A[(N - 1)/2 + 1]处

![[image-092b459d.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=100010;

int a[N];

int n;

int main()

{

    cin>>n;

    for(int i=0;i<n;i++)

        cin>>a[i];

    sort(a,a+n);

    int mid=a[n/2];

    LL res=0;

    for(int i=0;i<n;i++)

        res+=abs(a[i]-mid);

    cout<<res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/贪心相关模型/中位 平均/最小的和|最小的和]] 🏠 [[00-刷题理模型]] ➡️ [[区间分组|区间分组]]